package h0909;

import java.util.Arrays;

/**
  * @description 分割等和子集
  * @author 不知名帅哥
  * @date 2024/9/9 17:57
  * @version 1.0
*/
public class CutSameSumSubsets {
    public static void main(String[] args) {

    }
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum%2!=0) return false;
        int target=sum/2;
        boolean[] dp=new boolean[target+1];
        dp[0]=true;
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >=nums[i]; j--) {
                //表示是否可以找到一个子集，使得其和为 j。
                dp[j]=dp[j]||dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}
